package lanQiaoBei.数学知识.欧拉函数;
import java.io.*;
import java.util.*;
/*筛法求欧拉函数 https://blog.csdn.net/qq_62417282/article/details/128742135(解析)
*给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。

数据范围

1≤n≤1e6

输入样例：

6
输出样例：

12
* */
public class P2 {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    final static int N=1000010;
    static int primers[]=new int[N],phi[]=new int[N],cnt;
    static boolean st[]=new boolean[N];
    static void scan()throws Exception{

    }
    public static void main(String[]args)throws Exception{
           int n=Integer.parseInt(br.readLine());

           phi[1]=1;
           for(int i=2;i<=n;i++){
               if(!st[i]){
                   primers[cnt++]=i;
                   phi[i]=i-1;
               }
               for(int j=0;primers[j]<=n/i;j++){
                   st[primers[j]*i]=true;
                   if(i%primers[j]==0){
                       phi[primers[j]*i]=phi[i]*primers[j];
                       break;
                   }else{
                       phi[primers[j]*i]=phi[i]*(primers[j]-1);
                   }
               }
           }
           int res=0;
           for(int i=1;i<=n;i++){
               res+=phi[i];
           }
           System.out.print(res);
    }
}
